1. Field of the Invention
This invention relates to two-dimensional finite impulse response filter arrangements for filtering a signal that represents an image and comprises a sequence of digital words.
2. Description of the Prior Art
It is known to digitize a signal obtained by scanning a two-dimensional image, for example a television signal, by sampling the signal at a sampling frequency fs, that is, at predetermined intervals or clock periods T (where T=1/fs), to provide a digital image signal that comprises a sequence of digital words or samples (for example 8-bit words or samples) spaced in time by the interval T. Such an image signal can conveniently be manipulated. It can, for example, be reduced in size (compressed) in either or both dimensions, namely horizontally (that is in the direction in which the image is scanned in a line-sequential manner) or vertically (that is, transverse to the image scanning direction), for instance in the creation of digital video effects. As will now be described, however, in the absence of a suitable corrective measure, compression of the image can give rise to aliasing.
Thus, an image can be characterised by a two-dimensional parameter known as spatial frequency, which is proportional to the reciprocal of the angle subtended to the eye of the viewer by the visual spectral components of the image. The concept of spatial frequency can more readily be appreciated by considering an image in the form of a series of uniformly spaced straight lines. For a fixed position of the viewer with respect to such an image, the image has a single spatial frequency which is inversely proportional to the apparent spacing of the lines. (The spatial frequency is horizontal if the lines are vertical and spaced horizontally, vertical if the lines are horizontal and spaced vertically, and diagonal in other cases.) Clearly, if the image is compressed, so that the lines appear to the viewer to become closer together whereby the angle they subtend to the eye of the viewer decreases, the spatial frequency increases.
The scaling theorem in Fourier analysis states that if an image signal is compressed in the spatial domain, that is the spatial frequency of the image is increased, then the Fourier transform of the signal increases in the frequency domain (that is, the frequency (in Hz) of the signal increases); and vice versa.
The image signal discussed above is a sampled signal, and Nyquist's Rule concerning the sampling of signals states that, in order not to lose information contained in a signal, the signal must be sampled at a frequency (fs) that is equal to at least twice the highest frequency of the signal, or twice the bandwidth (fB) of the signal. This criterion is complied with when the digital input signal is formed initially by horizontally sampling an analog signal. The frequency spectrum (Fourier transform) of the sampled signal in the frequency domain is shown by the solid lines in FIG. 1 of the accompanying drawings, which is a graph of amplitude v. frequency (Hz). The frequency spectrum comprises a baseband component 10 (up to fB). Also, the baseband is reflected symmetrically around the sampling frequency fs and its harmonics 2fs, 3fs etc. to produce higher frequency components 12. Provided that Nyquist's Rule is complied with (so that fs/2 is greater than fB) and provided that the signal is band-limited (low-pass filtered) so as to have a cut-off frequency of about fs/2, the higher frequency components 12 will be suppressed.
As explained above, when the sampled signal is subjected to compression in the spatial domain, its Fourier transform exhibits expansion in the frequency domain. Thus, the bandwidths of the components 10 and 12 in FIG. 1 increase. As shown by dotted lines in FIG. 1, this can result in aliasing of the signal, in that the bandwidth fB of the signal can exceed the Nyquist limit (fs/2), so that part of at least the lowest one of the higher frequency components 12 extends down into and is mixed with the baseband 10 so as to degrade the signal and therefore the image that it represents.
To prevent aliasing due to compression, a filter can be positioned in advance of the compression means to filter out those parts of the two-dimensional input spectrum that otherwise would exceed the Nyquist limit frequency (fs/2) once compression has been carried out. Ideally, the filter should have a flat pass band, infinite attenuation in the stop band and a transition band whose width approaches zero. Naturally, such an ideal filter cannot be realized in practice. However, by using a two-dimensional (2D) finite impulse response (FIR) filter, an adequate filter characteristic can be obtained.
A 2D-FIR filter is operative during successive clock periods equal to T(=1/fs) to effect filtration over a predetermined area of the 2D image or picture by processing a set of words or samples of the image signal having a predetermined spatial relationship, to produce therefrom a filtered output word or sample. Specifically, during each clock period, the 2D-FIR filter is operative to calculate an output word or sample by multiplying a predetermined set (an array) of vertically and horizontally spaced words or samples of its input signal by respective weighting coefficients and summing the products of the multiplication operations. The necessary temporal delays to achieve the desired spatial relationship of the predetermined set of input words or samples can be achieved by delay elements positioned either in advance of or after respective multipliers used to carry out the multiplication operations. The delay elements can thus be considered to "tap" the image signal, in both directions. The response of the filter approaches more closely that of an ideal filter as the number of taps is increased.
Consider a compression means (for example a digital video effects unit) that is required to carry out compression over a range from zero compression (1:1) to, say, 100:1, the extent of compression being selectable in, for example, an infinitely variable manner. Consider also that the compression means is preceded by a 2D-FIR filter whose bandwidth is adjusted in accordance with the extent or degree of compression so as to avoid or at least reduce aliasing which otherwise would occur, in the event of compression, in the manner described above. In practice, it would not be feasible to design the filter so that its bandwidth is infinitely variable so that it can follow precisely the infinitely variable extent of compression. However, it would be feasible to design a 2D-FIR filter that would have a family of bandwidths (that is, that would be capable of producing a family of responses) each corresponding to a respective range of compression. (In this connection, as is known, the bandwidth of an FIR filter of a given configuration is determined by the values chosen for the weighting coefficients, whereby a family of responses can be obtained by previously calculating and storing a corresponding family of weighting coefficient sets). Thus, the filter might for example be designed to produce a family of bandwidths ranging from fs/2 (for zero compression) to fs/200 (for 100:1 compression). FIGS. 2A, 2B, 2C and 2D of the accompanying drawings show (in idealized form) responses that might be obtained for respective extents of compression of 1:1, 2:1, 3:1 and 100:1.
It should be appreciated that the image may be compressed in either or both of the horizontal and vertical directions, possibly by different respective degrees; and that a 2D-FIR filter has both horizontal and vertical bandwidths which may be varied independently of one another by suitably choosing the values of the weighting coefficients. Thus, it should be appreciated that the comments made above (and below) relating to bandwidth and compression apply independently to the horizontal and vertical directions, respectively.
The bandwidth of a system for handling a two-dimensional (vertical/horizontal) sampled image signal can be represented in the spatial domain by a two-dimensional frequency response as represented in FIG. 3 of the accompanying drawings. In FIG. 3, the horizontal axis represents a scale of horizontal spatial frequency in the positive and negative senses (H+ and H-) in units of cycles per picture (image) width; the vertical axis represents a scale of vertical spatial frequency in the positive and negative senses (V+ and V-) in units of cycles per picture (image) height; the rectangle 14 represents the two-dimensional bandwidth of the system; and the dimensions 16 and 18 represent the vertical and horizontal bandwidths, respectively. If the system comprises a 2D-FIR filter the vertical and horizontal bandwidths can be controlled by varying the values of the weighting coefficients. However, if the bandwidth is to be varied over a large range, for example over the range from fs/2 to fs/200 quoted above, and if the filter response is to be a reasonable approximation to the ideal response over the whole range, a very large number of tape is required. Accordingly, since, for each direction, the amount of hardware is approximately proportional to the number of taps, the filter would be very large and expensive.
To overcome this problem we have previously proposed in our UK patent specification GB-A-No. 2 184 316 a 2D-FIR filter arrangement for filtering a signal that represents an image and comprises a sequence of digital words spaced in time by an interval T, the filter arrangement comprising a 2D-FIR filter operative during each of a plurality of successive clock periods equal to T to effect filtration over a predetermined area of the image by processing a set of words of the image signal having a predetermined spatial relationship to produce therefrom an intermediate word; storage means for storing at least some of the intermediate words produced during the successive clock periods; and control means responsive to a signal indicating an extent to which the image is to be compressed to cause the FIR filter to adopt a bandwidth which is reduced, with respect to a value of the bandwidth for zero compression, by an extent related to the extent of compression, and to cause a plurality of the intermediate words, the size of which plurality is related to the extent of compression, to be combined so as to produce output words representative of filtration over a larger area of the image which is a multiple of said predetermined area.
Such a 2D-FIR filter arrangement takes advantage of the fact that, when an image signal is to be subjected to substantial compression, some of the samples or words thereof are not needed. Accordingly, the filter arrangement produces output words which each comprise a combination of intermediate words generated during respective clock periods. Thus, each output word is representative of filtration over an area of the image which is a multiple of the predetermined area corresponding to the set of words processed during each clock period. In other words, each output word effectively is equivalent to a word which would have been obtained if the number of taps of the 2D-FIR filter had been increased by the same multiple. Thus, the filter arrangement operates as if the number of taps were increased as the extent of the compression (the compression factor) is increased. Therefore, effectively by what could be termed "recycling" of the hardware, a filter arrangement comprising a filter having a number of taps sufficient for use in the case of zero or low compression can function effectively over a wide range of compression factors where, with a conventional filter, many more taps would be needed to provide a satisfactory response.
Such a 2D-FIR filter arrangement further comprises a plurality of multipliers, and a coefficient store containing a plurality of different sets of weighting coefficients corresponding respectively to a plurality of different filter bandwidths. The control means is then operative to select from the coefficient store, for supply to the multipliers, a set of weighting coefficients that will cause the filter arrangement to have a bandwidth appropriately related to the extent of the compression.
In such a 2D-FIR filter arrangement, and indeed generally in 2D-FIR filter arrangements for filtering signals that represent images and comprise sequences of digital words, and which operate by multiplying input digital data by respective weighting coefficients derived from a store, the number of bits to be stored in the store can become excessively large. This is because the number of bits is determined by the product of the number of taps which the filter arrangement is to have in each of the two dimensions; the maximum filter size (which for an image signal is the product of the number of samples in the horizontal direction and the number of samples in the vertical direction in the image); the number of positions in the array of interpolated positions to be used; and the number of bits used to represent each weighting coefficient. Clearly this can result in an unacceptably large number of bits to be stored, or in the quality of the filter arrangement being reduced so as to bring the number of bits to be stored to an acceptable number.
An alternative which might be considered is the use of a variable separable filter. In such a filter the bandwidth can be well controlled in the horizontal and vertical directions, but cannot be very well controlled in diagonal directions. Such a filter cannot therefore be used where digital video effects are to be created, because if the image is rotated, out-of-band components from diagonal directions will go into the horizontal and vertical directions and cause aliasing.